动态规划：括号知多少
作者：alg-flody
编辑：Emily
请点击上面公众号，免费订阅。
主要推送关于对算法的思考以及应用的消息。培养思维能力，注重过程，挖掘背后的原理，刨根问底。本着严谨和准确的态度，目标是撰写实用和启发性的文章，欢迎您的关注。
01
—
你会学到什么？
在上一消息推送中，我们通过《装水最多的容器》这个实际问题，初步了解了动态规划的魅力所在，还记得如果我们枚举所有可能的容器高度和边长时得到算法时间复杂度很大，而经过仔细分析目标函数和其变量关系时，我们发现把初始值设置为最大底边长度乘以相对小的高度后，之后的迭代中最大面积的容器只可能出现在尽可能高的情况下，如下动画所示，初始值为12，然后动态地交替地调整两个边（指针），目的是牺牲底的长度，尽量获得大的容器高度，从而得到更大的容器，果然在索引为2，和5时，容器的最大高度为 24 。
在本推送中，我们继续体验动态规划这个算法思想，领域经过仔细分析思考后的算法性能的优越，往往直观的第一下想到的算法不是很优秀的算法，当然排除那些大牛，毕竟他们已经形成了优秀算法的思维，这是我们努力的方向。
02
—
讨论的问题是什么？
讨论动态规划思想到底该怎么应用到实际问题当中。怎么拿到一个问题，然后就能想到用动态规划区解决呢？
这次探讨的这个实际问题，比较有意思，是给出一堆括号，让你分析出最长的括号长度，当然是辨识出有效的括号长度。
03
—
实际问题描述
先看原题，摘自LeetCode官网：
Given a string containing just the characters
'('and')', find the length of the longest valid (well-formed) parentheses substring.For
"(()", the longest valid parentheses substring is"()", which has length = 2.Another example is
")()())", where the longest valid parentheses substring is"()()", which has length = 4.
题目的意思是求出有效括号的长度的最大值，举了几个例子：
(() 有效长度为2
)()()) 有效长度为4
((()()()) 有效长度为8
初步分析
看到这个问题，首先要想一个问题，给定一个字符串，怎么判断这个字符串是否是有效的字符串括号呢？
借助栈，如果是 ( 将之推到栈中，如果是 ) ，判断栈顶是 ( 吗，如果是，则表明找到一对有效的组合并出栈 (；如果不是，说明这个不是有效字符括号串，或者栈为空了，进来一个 )，也表明不是有效的字符串。
找到判断一个字符串是否是有效的方法后，当然可以穷举这个字符串括号的所有子字符串，这个过程就得 O(n^2) 的时间复杂度，大家可以想下，这个算法肯定不是高效的。
那么，有没有更好的算法呢？
04
—
括号知多少
大家想下上面的那个判断一个括号串的算法，会不会有更简单的实现。
有的。如果一个括号串的结尾是 (，那么这个括号串一定不是有效的串；
所以，有效的括号串一定得以 ) 结尾才行。
因此，我们定义一个数组 dp[n] ，n为字符个数。 dp[i]表示的含义：以索引i结尾的子字符串的最长长度。
因为上文提到过，有效字符串一定得以 ) 结尾，并且先研究两个连续相邻的字符（至于为什么，请看下面的具体讨论），所以我们只需要讨论两种情况，即
()
))
具体说来如下，
如果 str[i] = ')'，并且 str[i-1] = '('，比如 ...()()，在这种情况下的状态转换方程为
dp[i] = dp[i-2] + 2
如果 str[i] = ')'，并且 str[i-1] = ')'，比如 ...))，
如果再满足 str[ i - dp[i-1] - 1] = '('，比如 .....(()())，这种情况的状态转化方程为
dp[i] = dp[i-1] + 2 + dp[ i- dp[i-1] -2]
这种情况不是很好理解，请参考下图理解，可以看到 索引 i 此时等于 7，
dp[7] = dp[6] + 2 + dp[7 - dp[6] - 2]
至此这个问题，借助动态规划的思想，通过找到状态的转移方程，我们便找到了问题的解，这个问题的转化公式由以上两种情况组成。
05
—
源码实现
有了以上的分析和动态转移方程，代码便出来了，如下所示：
public int longestValid(String s){
int maxlen = 0;
int dp[] = new int[s.length()];
for(int i=1; i<s.length();i++){
if(s.charAt(i)==')'){ //这是第一个大条件
//情况1
if(s.charAt(i-1)=='('){
dp[i] = (i>=2? dp[i-2]:0)+2;
}//情况2
else if(i-dp[i-1]>0 &&
s.charAt(i-dp[i-1]-1)=='('){
int tmp = i-dp[i-1]>=2?
dp[i-dp[i-1]-2]:0+2;
dp[i] = dp[i-1] + 2 + tmp;
}
maxlen = Math.max(maxlen, dp[i]);
}
}
return maxlen;
}
06
—
总结
以上动态规划算法的时间复杂度为 O(n)，空间复杂度为 O(n) 。算法通过分析得出满足一定条件下的两个不同的状态转移方程，然后动态的求出子字符串的最大有效括号长度，这便是动态规划的思想之所在。
以上算法思想部分参考LeetCode。
07
—
GitChat
这是我发起的一次Chat，诚邀您的参与！
最常用的 8 个排序算法：从原理到改进，再到代码兑现透彻解析
越到最后，你越会明白算法和数据结构很 cool，很 essential。这些都是内功，和用什么语言、技术或框架无关。本场 Chat 的主要内容包括：
8 个主要排序算法的思想和原理图解，代码兑现
从冒泡排序到快速排序做的那些优化
从直接选择排序到堆排序做的那些改进
从直接插入排序到希尔排序做的那些改进
归并排序算法的过程图解
不基于比较的基数排序原理图解
PC端扫描上图左下角的二维码，手机端长按此二维码，进入页面。谢谢。
欢迎关注《算法channel》公众号
主要推送关于对算法的思考以及应用的消息。培养思维能力，注重过程，挖掘背后的原理，刨根问底。本着严谨和准确的态度，目标是撰写实用和启发性的文章，欢迎您的关注。